#include <new>
#include <iostream>

using namespace std;

class nomemory {};

enum { alignment = sizeof(int) };

class dumballoc {
  typedef unsigned int word;
  struct fbhdr { // free block header
    long size;   // единица измерения -- слово sizeof(word)
    word *next;
    fbhdr(long size, word *next): size(size), next(next) {}
  };
  struct obhdr { // occupied block header
    long size;
    obhdr(long size): size(size) {}
  };
  enum {
	 fbhdrsize = sizeof(fbhdr) / sizeof(word),
	 obhdrsize = sizeof(obhdr) / sizeof(word) };
  word *pool;
  word *ff;
  static long words(long bytes) { return (bytes - 1) / sizeof(word) + 1; } // переводит в слова, округляя вверх
  static long bsize(word *b) { return ((fbhdr *)b)->size; } // возвращает размер блока, нужна, чтобы не делать каждый раз приведение типов
public:
  dumballoc(long size);
  void *alloc(long size);
  void free(void *);
  void dump(ostream &s) const;
};

dumballoc::dumballoc(long size):
  pool(new word[words(size)]),
  ff(pool)
{
  new (pool) fbhdr(words(size), 0);
}

void *dumballoc::alloc(long nbytes)
{
  // размер блока в словах: сколько запросили плюс размер заголовка, но не меньше, чем размер заголовка свободного блока, потому чтобы при освобождении должно хватить места под заголовок
  long bs = max(words(nbytes) + words(sizeof(obhdr)), words(sizeof(fbhdr)));
  cout << "bs = " << bs << endl;
  fbhdr *b = (fbhdr *)ff; // первый свободный -- наш кандидат
  word **bp = &ff; // при вставке в односвязный список нужен указатель на указатель на текущий блок
  while (b && b->size != bs &&
	 b->size - bs < fbhdrsize) { // перестаем искать, когда список кончился, либо когда найден идеально подходящий блок, либо когда найдет блок, после разбиения которого останется место для заголовка свободного блока
    bp = &b->next;
    b = (fbhdr *)b->next;
  }
  if (!b) throw nomemory();
  word *block = (word *)b;
  if (b->size == bs) // если найден блок как раз нужного размера, то тупо выкидываем его из списка
    *bp = b->next;
  else {
    word *rest = (word *)b + bs;                 // иначе бьем блок: размечаем его конец
    new (rest) fbhdr(b->size - bs, b->next);     // размещаем в конце заголовок
    *bp = rest;                                  // и корректируем указатель в предыдущем блоке
  }
  new (block) obhdr(bs); // ((obhdr *)block)->size = bs; размещаем в выделенном блоке заголовк
  return block + obhdrsize; // возвращаем указатель на место после заголовка
}

void dumballoc::free(void *p)
{
  word *ob = ((word *)p - obhdrsize); // находим заголовок
  word *b = ff;  
  word **bp = &ff;
  while (b && ob + bsize(ob) != b &&
	 b + bsize(b) != ob) {  // ищем пока не кончиться список, либо на найдется блок, расположенный по соседству справа или слева
    bp = &((fbhdr *)b)->next;
    b = ((fbhdr *)b)->next;
  }
  if (!b) { // не нашли, это значит что соседние блоки заняты, объединять ни с кем не нужно
    ((fbhdr *)ob)->next = ff;
    ff = ob;
  }
  else if (ob + ((obhdr *)ob)->size == b) { // если блок справа свободен, то объединяем
    ((fbhdr *)ob)->size += ((fbhdr *)b)->size;
    ((fbhdr *)ob)->next = ((fbhdr *)b)->next;
    *bp = (word *)ob;
  }
  else { // если блок слева свободен, то объединяем
    ((fbhdr *)b)->size += ((fbhdr *)ob)->size;
  }
  // Случай, когда освобождаемый блок окружен свободными блоками, не рассмотрен. Сделайте это самостоятельно.
}


// выводит дамп списка свободных блоков, адрес выводится в виде количества слов от начала пула, размеры не в байтах, а в словах sizeof(word).

void dumballoc::dump(ostream &s) const // нужно для отладки и для демонстрации картины распределения
{
  s << "== dump ==" << endl;
  fbhdr *b = (fbhdr *)ff;
  while (b) {
    fbhdr *hdr = (fbhdr *)b;
    s << "block: " << (word *)hdr - pool << ", size: " << hdr->size << endl;
    b = (fbhdr *)b->next;
  }
}

dumballoc A(1024*1024); // для четырехбайтового int'а это 262144 слов

int main()
{
  A.dump(cout); // тут мы ожидаем один блок размером в 262144 слова
  void *x = A.alloc(100);
  A.dump(cout); // тут тоже один блок, но уже размера 262144 - 27 (это 100 байт)
  void *y = A.alloc(100);
  A.dump(cout); // все еще один блок
  void *z = A.alloc(100);
  A.free(y);
  A.free(x);
  A.dump(cout); // а тут уже есть фрагментация: два куска свободного места -- ведь мы освободили первый и второй, а третий занят. Более того, так как первые два блока слились вместе, то в результате получился один свободный блок размером в 54 (27 + 27), и куча свободного места в конце.
  A.free(z);
  A.dump(cout); // а тут дела плохи: последний блок был окружен двумя свободными. Так как слияние с двум блоками не реализовано, то пул получился полностью свободным, но состоящим из двух блоков.
}
